package 组合总和II;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @author: AirMan
 * @date: 2025/4/13 18:12
 * @description: 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * candidates 中的每个数字在每个组合中只能使用一次。
 * 说明： 所有数字（包括目标数）都是正整数。解集不能包含重复的组合。
 */
public class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        // 回溯法
        // 回溯的参数：candidates，target，startIndex, result，path
        // 回溯的返回值：void
        // 回溯的终止条件：pathSum > target，说明不可能通过加一个正数达到 target。我们采用 target == 0 进行判断
        // 单层回溯的逻辑：横向遍历处理 candidates 中剩下的每一个元素
        // 纵向遍历就是从 candidates 中拿出元素继续进行相加
        // ① candidates[i] == candidates[i - 1] && !used[i - 1] 表示同一层使用过该数字
        // ② candidates[i] == candidates[i - 1] && used[i - 1] 表示同一层使用过该数字！
        // 加入 boolean[] used 数组让我们很好的将数值和数层分开了，只要递归进去那么前一个的boolean一定是true，只要是for循环
        // 进行的横向遍历，那么前一个的boolean一定因为回溯变为了false！

        if (target == 0) {
            return Collections.emptyList();
        }
        Arrays.sort(candidates);
        used = new boolean[candidates.length];
        Arrays.fill(used, false);
        backtarcking(candidates, target, 0);
        return result;
    }

    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used;

    public void backtarcking(int[] candidates, int target, int startIndex) {
        if (target == 0) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = startIndex; i < candidates.length; i++) {
            int newtarget = target - candidates[i];
            // 排序 + 剪枝
            if (newtarget < 0) {
                break;
            }
            // 数层去重
            if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) {
                System.out.println("同一数层 使用过该数字：" + candidates[i]);
                continue;
            }
            if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1]) {
                System.out.println("同一树枝 使用过该数字：" + candidates[i]);
            }
            used[i] = true;
            path.add(candidates[i]);
            // startIndex还是从i开始是因为，元素可以重复使用
            backtarcking(candidates, newtarget, i + 1);
            used[i] = false;
            path.remove(path.size() - 1);
        }
    }
}
